/**
 * @program: LeetCode
 * @description: LeetCode : 面试题 02.07. 链表相交
 * @author: WXY
 * @create: 2023-01-14 14:48
 * @Version 1.0
 * <p>
 * 给你两个单链表的头节点headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * 题目难度简单，因为题目中说明了，数据没有环状结构
 **/
public class Num02_07_getIntersectionNode {
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headB == null || headA == null) return null;

        ListNode head1 = headA;
        ListNode head2 = headB;
        int n = 0;
        while (head1.next != null) {   //head1 来到链表的结尾，
            head1 = head1.next;
            n++;
        }
        while (head2.next != null) {    //head2 来到链表的结尾，
            head2 = head2.next;
            n--;
        }
        if (head2 != head1) {   //head1 和 head2 都来到彼此的结尾处，如果不相等，必不相交
            return null;
        }
        //此时，相等，必定相交了，而n的值的绝对值就是  长链表长度 - 短链表长度
        // 哪个链表长，哪个就给head1，然后长链表先走 n 步
        head1 = n > 0 ? headA : headB;
        head2 = head1 == headA ? headB : headA;
        n = Math.abs(n);
        while (n != 0) {
            head1 = head1.next;
            n--;
        }

        while (head2 != head1) {
            head1 = head1.next;
            head2 = head2.next;
        }
        return head1;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
